package treeStudy;

import common.utils.TreeNode;

import java.util.Stack;

public class TreeStudy02 {

    /**
     * 面试题8：二叉树的下一个结点
     * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     * @param args
     */
    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode treeNode = TreeStudy01.recreateTree(pre, in);
        int i = inOrderNextNode(3, treeNode);
        System.out.println(i);
    }
    //方法一：通过非递归的中序深度优先遍历
    public static int inOrderNextNode(int target, TreeNode t){
        boolean flag = false;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode c = t;
        if (t == null)return -1;
        do {
            while (c != null){
                stack.push(c);
                c = c.left;
            }
            c = stack.pop();
            if (flag){
                return c.val;
            }
            if (target == c.val){
                flag = true;
            }
            //开始访问c的子树
            c = c.right;
        } while (c != null || !stack.isEmpty());
        return  -1;
    }
    //方法二：充分使用给定条件
    //分析：
    //如果结点A的右子树不为空，那么它的下一个结点就是右子树的最右结点
    //如果结点A的右子树为空，结点A就是以A为根的最右结点；那么A的下一个结点就是以A为最右结点的最小左子树的根结点
    //寻找以A为最右结点的最小左子树，就是向上追溯，A或A的某个祖先结点是某个结点的左子树
    //问题关键，确定以A为最右节点的最小左子树，找到父节点，改父节点的左孩子是不是该节点。
    /*public static int inOrderNextNode(int target, TreeNode t){

    }*/
}
